package cengxubianli

import "hufeng/ercahshu"

func rightSideView(root *ercahshu.TreeNode) []int {
	// 层序遍历+输出每行最后一个元素
	ans := make([]int, 0)
	if root == nil {
		return ans
	}
	node := root
	stack := make([]*ercahshu.TreeNode, 0)
	stack = append(stack, node)
	for len(stack) > 0 {
		var lastPtr *ercahshu.TreeNode
		n := len(stack)
		for i := 0; i < n; i++ {
			if stack[i].Left != nil {
				stack = append(stack, stack[i].Left)
			}
			if stack[i].Right != nil {
				stack = append(stack, stack[i].Right)
			}
			lastPtr = stack[i]
		}
		ans = append(ans, lastPtr.Val)
		stack = stack[n:]
	}
	return ans
}

func DFS(root *ercahshu.TreeNode) []int {
	ans := make([]int, 0)
	var dfs func(node *ercahshu.TreeNode, height int)
	dfs = func(node *ercahshu.TreeNode, height int) {
		if node == nil {
			return
		}
		if height == len(ans) {
			ans = append(ans, node.Val)
		}
		dfs(node.Right, height+1)
		dfs(node.Left, height+1)
	}
	dfs(root, 0)
	return ans
}
